package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
 * 参考题解：https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution
 * 中心扩散法通过
 *
 * @author yulongtian
 * @create 2024-07-28 11:29
 */
public class Test92 {
    public static void main(String[] args) {
        System.out.println(new Test92().longestPalindrome("baabad"));
    }

    /**
     * 暴力解法或中心扩散法
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int[] jishu = findPalindromeStartAndLen(s, i, i);
            int[] oushu = findPalindromeStartAndLen(s, i, i + 1);
            if (jishu[1] >= oushu[1]) {
                if (maxLen < jishu[1]) {
                    maxLen = jishu[1];
                    begin = jishu[0];
                }
            } else {
                if (maxLen < oushu[1]) {
                    maxLen = oushu[1];
                    begin = oushu[0];
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    public int[] findPalindromeStartAndLen(String s, int left, int right) {
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0 && j < len) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        return new int[]{i + 1, j - i - 1};
    }


}
